TNotes.leetcode

Appearance

0342. 4的幂【简单】

0342. 4的幂【简单】 ​

1. 📝 题目描述 ​

给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false。

整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4^x

示例 1：

txt
输入：n = 16
输出：true

示例 2：

txt
输入：n = 5
输出：false

示例 3：

txt
输入：n = 1
输出：true

提示：

  • -2^31 <= n <= 2^31 - 1

进阶：你能不使用循环或者递归来完成本题吗？

2. 🎯 s.1 - 循环除法 ​

js
/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfFour = function (n) {
  // 4 的幂必须是正整数
  if (n <= 0) return false

  // 不断除以 4，直到不能整除为止
  while (n % 4 === 0) {
    n /= 4
  }

  // 如果最后结果是 1，说明原来是 4 的幂
  return n === 1
}
  • 时间复杂度：O(log4⁡n)
  • 空间复杂度：O(1)

3. 🎯 s.2 - 递归法 ​

js
/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfFour = function (n) {
  // 4 的幂必须是正整数
  if (n <= 0) return false

  // 1 是 4 的幂 (4⁰)
  if (n === 1) return true

  // 不能被 4 整除，不是 4 的幂
  if (n % 4 !== 0) return false

  // 递归检查
  return isPowerOfFour(n / 4)
}
  • 时间复杂度：O(log4⁡n)
  • 空间复杂度：O(log4⁡n)，递归调用栈

4. 🎯 s.3 - 位运算 ​

js
/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfFour = function (n) {
  // 4 的幂必须是正整数
  if (n <= 0) return false

  // 必须是 2 的幂（二进制中只有一个 1）
  if ((n & (n - 1)) !== 0) return false

  // 4 的幂在二进制中，1 只出现在奇数位置
  // 0x55555555 的二进制是 01010101010101010101010101010101
  // 这个掩码的奇数位都是 1，偶数位都是 0
  return (n & 0x55555555) !== 0
}
  • 时间复杂度：O(1)
  • 空间复杂度：O(1)
  • 算法思路：
    • n 如果是 4 的幂，那么一定也是 2 的幂
    • n 是 2 的幂的前提下，又满足 4 的幂具有的特性（二进制的 1 在奇数位上），那么 n 就是 4 的幂

5. 🎯 s.4 - 数学性质 ​

js
/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfFour = function (n) {
  // 4 的幂必须是正整数
  if (n <= 0) return false

  // 必须是 2 的幂
  if ((n & (n - 1)) !== 0) return false

  // 4 的幂满足 (n - 1) % 3 === 0
  // 这是因为 4^n - 1 = (2^n - 1)(2^n + 1)
  // 其中 2^n - 1 和 2^n + 1 必有一个是 3 的倍数
  return (n - 1) % 3 === 0
}
  • 时间复杂度：O(1)
  • 空间复杂度：O(1)
  • 算法思路：类似题解 3
    • n 如果是 4 的幂，那么一定也是 2 的幂
    • n 是 2 的幂的前提下，又满足 4 的幂具有的特性（(n - 1) % 3 === 0），那么 n 就是 4 的幂
js
// 【1】 n 是 2 的幂 <=> 【2】 (n & (n - 1)) === 0
// 【2】 是 【1】 的充分必要条件

// 【3】 n 是 4 的幂 => 【4】 (n - 1) % 3 === 0
// 【4】 是 【3】 的必要非充分条件

// 解释说明：
// 这是因为 4^k - 1 = (2^k - 1)(2^k + 1)
// 其中 (2^k - 1) 和 (2^k + 1) 必有一个是 3 的倍数
// 因为连续的 3 个整数中，必有一个是 3 的倍数。
// 连续的 3 个整数：(2^k - 1)、(2^k)、(2^k + 1)
// 中间的 (2^k) 必然不是 3 的倍数
// 所以剩余俩之间，必有一个是 3 的倍数

// 注意：
// 如果 n 同时满足 【2】、【4】，那么 n 必是 4 的幂
// 如果 n 单独满足 【4】 是推断不出 【3】 的，比如 n 为 7
// 如果 n 是 2 的幂（满足 【2】），并且 n 具备 4 个幂的特性（满足 【4】），那么 n 必是 4 的幂

return (n & (n - 1)) === 0 && (n - 1) % 3 === 0

Discussions